with Unchecked_Deallocation, Ada.Text_Io, Ada.Integer_Text_Io;
use Ada.Text_Io, Ada.Integer_Text_io;
package body Generic_Sorted_List is

   procedure Deallocate is new
     Unchecked_Deallocation(List_Type, List_Pointer);


   function Empty(List : in  List_Pointer) return Boolean is
   begin
      if List = null then
         return True;
      else
         return False;
      end if;
   end Empty;


   function Length(List : in List_Pointer) return Integer is
      Counter : Integer := 0;
      Tmp : List_Pointer := List;
   begin
      loop
         exit when Empty(Tmp);
         Counter := Counter + 1;
         Tmp := Tmp.Next;
      end loop;
      return Counter;
   end Length;


   procedure Insert(List : in out List_Pointer; In_Data : in Data_Type) is
      Prev, Next, Tmp : List_Pointer;
   begin
      Prev := List;
      Next := List;
      if Empty(List) then
         Tmp := new List_Type'(In_Data, null);
         List := Tmp;
      elsif (In_Data < Next.Data) then
         Tmp := new List_Type'(In_Data, List);
         List := Tmp;
      else
         Next := Next.Next;
         loop
            if Empty(Next) or else (In_Data < Next.all.Data) then
               Tmp := new List_Type'(In_Data, Next);
               Prev.Next := Tmp;
               exit;
            elsif In_Data = Next.all.Data then
               exit;
            else
               Prev := Prev.Next;
               Next := Next.Next;
            end if;
         end loop;
      end if;
   end Insert;

  procedure Put(List : in List_Pointer) is
      Tmp : List_Pointer := List;
   begin
      if not Empty(Tmp) then
         while not Empty(Tmp) loop
            Put(Tmp.Data);
            New_Line;
            Tmp := Tmp.Next;
         end loop;
      end if;
   end Put;

   function Member(List : in List_Pointer; key : in Key_Type) return Boolean is
      Tmp : List_Pointer := List;
   begin
      for I in 1..Length(Tmp) loop
         if Get_Key(Tmp.Data) = Key then
            return True;
         end if;
         Tmp := Tmp.Next;
      end loop;
      return False;
   end Member;

   procedure Remove(List : in out List_Pointer; Key : in Key_Type) is
      Prev : List_Pointer := List;
      Next : List_Pointer := List;
   begin
      if Empty(List) then
         raise Remove_Error;
      else
         if Key = Get_Key(List.Data) then
            List := List.Next;
            deallocate(Next);
         else
            Next := Next.Next;
            loop
               if Empty(Next) then
                  raise Remove_Error;
               elsif Key = Get_Key(Next.Data) then
                  Prev.Next := Next.Next;
                  Deallocate(Next);
                  exit;
               else
                  Prev := Next;
                  Next := Next.Next;
               end if;
            end loop;
         end if;
      end if;
   end Remove;


    procedure Delete(List : in out List_Pointer) is
      Tmp : List_Pointer;
   begin
      for I in 1..Length(List) loop
         Tmp := List;
         List := List.Next;
         deallocate(Tmp);
      end loop;
   end Delete;

   function Find(List : in List_Pointer; Key : in Key_type) return Data_Type is
     Tmp : List_Pointer := List;
   begin
      for I in 1..Length(Tmp) loop
         if Key = Get_Key(Tmp.Data) then
            return Tmp.Data;
         else
            Tmp := Tmp.Next;
         end if;
      end loop;
      raise Find_Error;
   end Find;

   procedure Find(List : in out List_Pointer;
                  Key : in Key_Type;
                  Output : out Data_Type) is
   begin
      Output := Find(List, Key);
   end Find;

   procedure Next(List : in out List_Pointer) is
   begin
      List := List.Next;
   end Next;

   procedure Copy(Orig : in out List_Pointer; Copy : in out List_Pointer) is
      Tmp_Orig : List_Pointer := orig;
      Data_Copy : Data_Type;
   begin
      if not Empty(Copy) then
         Delete(Copy);
      end if;
      while not Empty(Tmp_Orig) loop
         Data_Copy := Tmp_Orig.Data;
         Insert(Copy, Data_Copy);
         Tmp_Orig := Tmp_Orig.Next;
      end loop;
   end Copy;

   function Copy(Orig : List_Pointer) return List_Pointer is
      Copy : List_Pointer;
      Tmp_Orig : List_Pointer := orig;
      Data_Copy : Data_Type;
   begin
      if not Empty(Copy) then
         Delete(Copy);
      end if;
      while not Empty(Tmp_Orig) loop
         Data_Copy := Tmp_Orig.Data;
         Insert(Copy, Data_Copy);
         Tmp_Orig := Tmp_Orig.Next;
      end loop;
      return Copy;
   end Copy;

   function Get_First_Item(List : in List_pointer) return Data_Type is
      Tmp : List_Pointer := list;
   begin
      return Tmp.Data;
   end Get_First_Item;

end Generic_Sorted_List;

